//  https://leetcode-cn.com/problems/missing-number/
//  MissNumber.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/7/31.
//  Copyright © 2019 XFB. All rights reserved.
//  缺失数字

import Foundation

class MissNumber {
    
    /**
     给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
     示例 1:
     输入: [3,0,1]
     输出: 2
     
     示例 2:
     输入: [9,6,4,2,3,5,7,0,1]
     输出: 8
     */
    
    func missingNumber(_ nums: [Int]) -> Int {
        
        /// 长度应该是4    1 2 3 4 现在只有三个
        let length = nums.count
        var sum = 0
        /// 等差数列的求和 (a1 + an) / 2 * n
        let totalSum = length * (length + 1) / 2
        for i in 0 ..< length {
            sum = sum + nums[i]
        }
        return totalSum - sum
    }
    
    
    //
    func missingNumber1(_ nums: [Int]) -> Int {
        
        /// 长度应该是4    1 2 3 4 现在只有三个
        let length = nums.count
        var totalSum = 0
        
        for i in 0 ..< length + 1 {
            totalSum = totalSum + i
        }
        
        for i in 0 ..< length {
            totalSum = totalSum - nums[i]
        }

        return totalSum
    }
    
}
